package 链表;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 */

public class _234_回文链表 {

    /**
     * 使用双指针方法
     * 将链表存到数组中，通过下标来对比
     * @param head 目标链表
     * @return boolean
     */
    public static boolean isPalindromeByTow(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode node = head;
        List<ListNode> list = new ArrayList<>();
        while (node != null) {
            list.add(node);
            node = node.next;
        }

        int length = list.size();
        for (int i = 0; i < length / 2; i++) {
            if (list.get(i).val != list.get(length - 1 - i).val) {
                return false;
            }
        }
        return true;
    }


    /**
     * 快慢指针  通过查询中间值，让后半部分进行反转，然后一一对比
     * @param head 目标链表
     * @return boolean
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 查询链表中间
        ListNode helfOfList = endOfFirstHead(head);
        // 链表反转
        ListNode reverseList = reverseList(helfOfList.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = reverseList;
        boolean ret = true;
        while (ret && p2 != null) {
            if (p1.val != p2.val) {
                ret = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        // 链表转回去
        helfOfList.next = reverseList(reverseList);
        return ret;
    }

    /**
     * 链表反转
     * @param head 链表
     * @return ListNode
     */
    private ListNode reverseList(ListNode head) {
        ListNode curr = head;
        ListNode prev= null;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }

    /**
     * 获取链表中间部分
     * @param head 目标链表
     * @return ListNode
     */
    private ListNode endOfFirstHead(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
